#ifndef LEETCODE_CN_CPP_PROBLEMS_84_H
#define LEETCODE_CN_CPP_PROBLEMS_84_H

#include <algorithm>
#include <vector>

using namespace std;

namespace problem_84
{

class Solution
{
private:
    vector<int> stack;
    vector<int> leftBoundaries;
    vector<int> rightBoundaries;
    void getBoundaries(vector<int> &heights)
    {
        stack.clear();
        rightBoundaries.resize(heights.size(), 0);
        for (int i = 0; i < heights.size(); ++i)
        {
            while (!stack.empty() && heights[stack.back()] > heights[i])
            {
                rightBoundaries[stack.back()] = i - 1;
                stack.pop_back();
            }
            stack.push_back(i);
        }
        stack.clear();
        leftBoundaries.resize(heights.size(), 0);
        for (int i = heights.size() - 1; i >= 0; --i)
        {
            while (!stack.empty() && heights[stack.back()] > heights[i])
            {
                leftBoundaries[stack.back()] = i + 1;
                stack.pop_back();
            }
            stack.push_back(i);
        }
    }

public:
    int largestRectangleArea(vector<int> &heights)
    {
        heights.push_back(0);
        getBoundaries(heights);
        int maxArea = 0;
        for (int i = 0; i < heights.size(); ++i)
        {
            maxArea = max(maxArea, heights[i] * (rightBoundaries[i] - leftBoundaries[i] + 1));
        }
        heights.pop_back();
        return maxArea;
    }
};

} // namespace problem_84

#endif //LEETCODE_CN_CPP_PROBLEMS_84_H
